<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    //封装二叉搜索树
    function binarySearchTree() {
         function Node(key) {
              this.key = key
              this.left = null
              this.right = null
         }
         //属性
        this.root = null

        //方法
        binarySearchTree.prototype.insert = function (key) {
            // 1.根据key创建节点
            var newNode = new Node(key)

            // 2.判断根节点是否有值
            if(this.root == null){
                this.root = newNode
            } else {
                this.insertNode(this.root,newNode)
            }
        }

        binarySearchTree.prototype.insertNode = function (node,newNode) {
                 if(newNode.key < node.key){  //向左查找
                     if(node.left == null){
                         node.left = newNode
                     }else{
                         this.insertNode(node.left,newNode)
                     }
                 } else { //向右查找
                      if(node.right == null){
                          node.right = newNode
                      }else{
                          this.insertNode(node.right,newNode)
                      }
                 }
        }
        //先序遍历
        binarySearchTree.prototype.preOrderTraversal = function (handler) {
                this.preOrderTraversalNode(this.root,handler)
        }

        binarySearchTree.prototype.preOrderTraversalNode = function (Node,handler) {
               if(Node != null){
                   //记录节点
                   //
                   // str +=Node.key
                   handler(Node.key);
                   this.preOrderTraversalNode(Node.left,handler);
                   this.preOrderTraversalNode(Node.right,handler);
               }
        }
        //中序遍历
        binarySearchTree.prototype.midOrderTraversal = function (handler) {
            this.midOrderTraversalNode(this.root,handler)
        }

        binarySearchTree.prototype.midOrderTraversalNode = function (Node,handler) {
            if(Node != null){
                //记录节点
                this.midOrderTraversalNode(Node.left,handler);
                handler(Node.key);
                this.midOrderTraversalNode(Node.right,handler);
            }
        }
        //后序遍历
        binarySearchTree.prototype.postOrderTraversal = function (Node,handler) {
            this.postOrderTraversalNode(this.root,handler)
        }

        binarySearchTree.prototype.postOrderTraversalNode = function (Node,handler) {
            if(Node != null){
                //记录节点

                this.preOrderTraversalNode(Node.left);
                this.preOrderTraversalNode(Node.right);
                handler(Node.key);
            }
        }

        //查找最值
        //查找最大值
        binarySearchTree.prototype.max = function () {
             //获取跟节点
             var Root = this.root;

             while (Root.right != null){
                 Root = Root.right
             }
             return Root.key;
        }
        //查找最小值
        binarySearchTree.prototype.min = function () {
            //获取跟节点
            var Root = this.root;

            while (Root.left != null){
                Root = Root.left
            }
            return Root.key;
        }

        //搜索一个key是否存在
        binarySearchTree.prototype.search = function (key) {
             
               var node = this.root

               while (node != null){
                     if(key < node.key){
                         node = node.left
                     }else if(key > node.key){
                         node = node.right
                     }else{
                         return true
                     }
               }
        }

        //删除节点
        binarySearchTree.prototype.remove = function (key) {
                 // 1.寻找要删除的节点
                 // 1.1定义变量，保存一些信息
                 var current = this.root;
                 var parent = null;
                 var isLeftChild = true;

                 // 2.根据对应的情况删除节点
                 while(current.key != key){
                     parent = current
                     if(key < current.key){
                         isLeftChild=true;
                         current = current.left
                     }else{
                         isLeftChild=false;
                         current = current.right
                     }
                     //某种情况: 已经找到了最后的节点,依然没有找到==key
                     if(current == null) return false
                 }
               // 2.根据对应的情况删除节点
               // 2.1.删除的节点是叶子节点(没有子节点)
               if(current.left == null && current.right == null){
                   if(current == this.root){
                       this.root = null
                   }else if(isLeftChild){
                       parent.left = null
                   }else{
                       parent.right = null
                   }
               }
               // 2.2.删除的节点有一个子节点
              else if(current.right == null){
                  if(current == this.root){
                      this.root = current.left
                  }else if(isLeftChild){
                      parent.left = current.left
                  }else{
                      parent.right = current.left
                  }
               }else if(current.left == null){
                   if(current == this.root){
                       this.root = current.right
                   }else if(isLeftChild){
                      parent.left = current.right
                  }else{
                      parent.right = current.right
                  }
               }
               // 2.3.删除的节点有两个子节点
                else{
                    var successor = this.getSuccessor(current);

                    if(current == this.root){
                        this.root = successor
                    }else if(isLeftChild){
                        parent.left = successor
                    }else {
                        parent.right = successor
                    }

                     successor.left = current.left
               }
        }

        // 找后继方法
        binarySearchTree.prototype.getSuccessor = function (delNode) {
              // 1.定义变量 保存找到的后继
            var successor = delNode
            var current = delNode.right
            var successorParent = delNode

            // 2.循环查找
            while (current != null){
                successorParent = successor
                successor = current
                current = current.left
            }
            // 3.判断寻找的后继节点是否直接等于delNode的right节点
            if(successor != delNode.right){
                successorParent.left = successor.right
                successor.right = delNode.right
            }
            return successor
        }



    }
    var bst =  new binarySearchTree();
    var str = '';
    var handle = function (Key) {
         str += Key + '';
    }
    bst.insert(1)
    bst.insert(15)
    bst.insert(3)
    bst.insert(2)
    bst.insert(9)
    bst.insert(5)
    // bst.midOrderTraversal(handle)
    bst.preOrderTraversal(handle)
    alert(str);
</script>
</body>
</html>